/*
 * Created by guoyh on Sat Dec 03 2022
 * leetcode NO.77 https://leetcode.cn/problems/combinations/ 
 */
#include<vector>
#include<iostream>
#include<gtest/gtest.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> path;
        dfs(res, n, k, 1, path);
        return res;
    }

    // res: 保存最终结果，
    // n: 数值上限
    // k: 找k个数
    // index: 参加组合的数本身
    // path：保存组合
    void dfs(vector<vector<int>>& res, int n, int k, int index, vector<int>& path){
        if(path.size() == k){
            res.push_back(path);
            return;
        }

        for(int i = index; i <= n; i++){
            // 没有剪枝
            path.push_back(i);
            dfs(res, n, k, i + 1, path);
            path.pop_back();
        }

    }
};

TEST(Combination, Small1){
    Solution slu;
    vector<vector<int>> res = slu.combine(4,2);
    EXPECT_EQ(res.size(), 6);    
}

TEST(Combination, Small2){
    Solution slu;
    vector<vector<int>> res = slu.combine(5,5);
    EXPECT_EQ(res.size(), 11) << "combine(5,5) failed";

}

TEST(Combination, Small3){
    Solution slu;
    vector<vector<int>> res = slu.combine(20,20);
    EXPECT_EQ(res.size(), 10);
}

TEST(Combination, Large1){
    Solution slu;
    vector<vector<int>> res = slu.combine(20,10);
    EXPECT_EQ(res.size(), 184756);
}

TEST(Combination, Large2){
    Solution slu;
    vector<vector<int>> res = slu.combine(20,11);
    EXPECT_EQ(res.size(), 167960);
}

TEST(Combination, Large3){
    Solution slu;
    vector<vector<int>> res = slu.combine(20,9);
    EXPECT_EQ(res.size(), 167960);
}

TEST(Combination, Small4){
    Solution slu;
    vector<vector<int>> res = slu.combine(1,1);
    EXPECT_EQ(res.size(), 1);
}



int main(int argc, char *argv[]) {
  ::testing::InitGoogleTest(&argc, argv);
  return RUN_ALL_TESTS();
}

